package q23_mergeKLists;
import static CommonClass.Common.*;
public class Solution_1 {
    public static void main(String[] args) {
        ListNode a = generateList(new int[]{1,2,3});
        ListNode b = generateList(new int[]{2,3,4});
        ListNode c = generateList(new int[]{17,22,73});

        printList(mergeKLists(new ListNode[]{a,b,c}));
    }


    public static ListNode mergeKLists(ListNode[] lists) {

        if(lists.length == 0){
            return null;
        }

        if (lists.length == 1) {
            return lists[0];
        }

        if (lists.length == 2) {
            return mergeTwoLists(lists[0],lists[1]);
        }

        // 如果数组有两个以上的链表，则开始先合并前两个链表，并开始循环合并下一个，直到结束为止。
        ListNode res = mergeTwoLists(lists[0],lists[1]);
        for (int i = 0; i < lists.length - 2; i++) {
            // 循环合并
            res = mergeTwoLists(res, lists[i + 2]);
        }
        return res;
    }

    /**
     * 两个有序链表的合并方法
     */
    public static ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        if(list1 == null || list2 == null) {
            return list1 == null?list2:list1;
        }

        ListNode res = new ListNode(0);
        ListNode head = res;
        while ((list1 != null) && (list2 != null)) {

            if(list1.val > list2.val){
                res.next = new ListNode(list2.val);
                list2 = list2.next;
            }else {
                res.next = new ListNode(list1.val);
                list1 = list1.next;
            }
            res = res.next;
        }
        res.next = (list1 == null)?list2:list1;
        return head.next;
    }

}
